﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.InteropServices;
using System.Threading;

namespace EVB.Collections.Immutable
{
    /// <summary>
    /// Represents an immutable first-in-first-out (FIFO) collection of instances of the same arbitrary type.
    /// </summary>
    /// <typeparam name="T">Specifies the type of elements in the queue.</typeparam>
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(QueueDebugView<>))]
    [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
    [SuppressMessage("Microsoft.Naming", "CA1711:IdentifiersShouldNotHaveIncorrectSuffix")]
    public sealed class Queue<T> : IEnumerable<T>, IEnumerable, ICollection
    {
        private readonly Stack<T> _backwards;
        private readonly Stack<T> _forwards;

        [NonSerialized]
        private object _syncRoot;

        /// <summary>
        /// Empty immutable queue is a starting point for an immutable queue population.
        /// </summary>
        [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
        [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
        public static readonly Queue<T> Empty = new Queue<T>();

        private Queue() { }

        private Queue(Stack<T> f, Stack<T> b)
        {
            _forwards = f;
            _backwards = b;
        }

        /// <summary>
        /// Determines whether this <see cref="Queue{T}"/> collection is empty.
        /// </summary>
        public bool IsEmpty { get { return _forwards == null || _backwards == null; } }

        /// <summary>
        /// Returns the object at the beginning of the <see cref="Queue{T}"/> without removing it.
        /// </summary>
        public T Peek
        {
            get
            {
                if (IsEmpty)
                    throw new InvalidOperationException(Properties.Resources.QueueEmpty);

                return _forwards.Peek;
            }
        }

        /// <summary>
        /// Adds an object to the end of the <see cref="Queue{T}"/> and returns a new <see cref="Queue{T}"/>.
        /// </summary>
        /// <param name="value">The object to add to the <see cref="Queue{T}"/>.</param>
        /// <returns>A new <see cref="Queue{T}"/> with added object.</returns>
        public Queue<T> Enqueue(T value)
        {
            if (IsEmpty)
                return new Queue<T>(Stack<T>.Empty.Push(value), Stack<T>.Empty);

            return new Queue<T>(_forwards, _backwards.Push(value));
        }

        /// <summary>
        /// Removes the object at the beginning of the <see cref="Queue{T}"/> and returns a <see cref="Queue{T}"/> without that object.
        /// </summary>
        /// <returns>A <see cref="Queue{T}"/> without removed object.</returns>
        public Queue<T> Dequeue()
        {
            if (IsEmpty)
                throw new InvalidOperationException(Properties.Resources.QueueEmpty);

            var f = _forwards.Pop();
            return !f.IsEmpty
                       ? new Queue<T>(f, _backwards)
                       : (_backwards.IsEmpty ? Empty : new Queue<T>(_backwards.Reverse(), Stack<T>.Empty));
        }

        /// <summary>
        /// Copies the <see cref="Queue{T}"/> elements to a new array.
        /// </summary>
        /// <returns>A new array containing elements copied from the <see cref="Queue{T}"/>.</returns>
        /// <remarks>
        /// The <see cref="Queue{T}"/> is not modified. The order of the elements in the new array is the same as the order of the elements from the beginning of the <see cref="Queue{T}"/> to its end.
        /// This method is an O(n) operation, where n is <see cref="Count"/>.
        /// </remarks>
        public T[] ToArray()
        {
            if (IsEmpty)
                return new T[0];

            var forwards = _forwards.ToArray();
            var backwards = _backwards.ToArray();
            var result = new T[forwards.Length + backwards.Length];

            for (int i = 0; i < forwards.Length; i++)
                result[i] = forwards[i];
            for (int i = 0; i < backwards.Length; i++)
                result[forwards.Length + i] = backwards[i];

            return result;
        }

        /// <summary>
        /// Returns the number of elements in a <see cref="Queue{T}"/>.
        /// </summary>
        public int Count
        {
            get
            {
                return (_forwards != null ? _forwards.Count : 0)
                     + (_backwards != null ? _backwards.Count : 0);
            }
        }

        #region IEnumerable members

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.</returns>
        public IEnumerator<T> GetEnumerator()
        {
            foreach (T item in _forwards) yield return item;
            foreach (T item in _backwards.Reverse()) yield return item;
        }

        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>An <seealso cref="IEnumerator"/> object that can be used to iterate through the collection.</returns>
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

        #endregion

        #region ICollection members

        /// <summary>
        /// Copies the <see cref="Queue{T}"/> to an existing one-dimensional array, starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array that is the destination of the elements copied from <see cref="Queue{T}"/>.</param>
        /// <param name="index">The zero-based index in <paramref name="array"/> at which copying begins.</param>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than zero.</exception>
        /// <exception cref="ArgumentException">The number of elements in the source <see cref="Queue{T}"/> is greater than the available space from <paramref name="index"/> to the end of the destination <paramref name="array"/>.</exception>
        public void CopyTo(T[] array, int index)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            ToArray().CopyTo(array, index);
        }

        void ICollection.CopyTo(Array array, int index)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            ToArray().CopyTo(array, index);
        }

        bool ICollection.IsSynchronized
        {
            get { return true; }
        }

        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                    Interlocked.CompareExchange(ref _syncRoot, new object(), null);

                return _syncRoot;
            }
        }

        #endregion
    }
}